package com.leetcode.q240;

/**
 * <p> description: desc</p>
 *
 * @author tanzc
 * @date 2022/3/30
 **/
public class SearchMaxtrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        return searchMatrix(matrix, 0, n - 1, 0, m - 1, target);
    }

    public boolean searchMatrix(int[][] matrix, int x1, int x2, int y1, int y2, int target) {
        if (x1 > x2 || y1 > y2) {
            return false;
        }

        int xx1 = x1 + 1, xx2 = -1, yy1 = y1 + 1, yy2 = -1;

        for (int x = x1; x <= x2; x++) {
            if (matrix[y1][x] == target) {
                return true;
            } else if (matrix[y1][x] > target) {
                xx2 = x;
                break;
            }
        }
        if (xx2 == -1) {
            xx2 = x2;
        }

        for (int y = y1; y <= y2; y++) {
            if (matrix[y][x1] == target) {
                return true;
            } else if (matrix[y][x1] > target) {
                yy2 = y;
                break;
            }
        }
        if (yy2 == -1) {
            yy2 = y2;
        }

        return searchMatrix(matrix, xx1, xx2, yy1, yy2, target);
    }
}
